﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using UFPE.CIn.Abc.Primality.Util;
using System.Diagnostics;

namespace UFPE.CIn.Abc.Primality.Algorithms
{
    public class MillerRabin : BaseConfidenceAlgorithm
    {
        public override string AlgorithmName
        {
            get
            {
                return "Miller-Rabin";
            }
        }

        private static MillerRabin instance;

        public static MillerRabin Instance
        {
            get
            {
                if (instance == null)
                {
                    instance = new MillerRabin();
                }

                return instance;
            }
        }

        //
        // Setting probability of error to 1/4^25 == 1/2^50
        //
        public override bool IsPrime(BigInteger x)
        {
            return IsPrime(x, 25);
        }

        public override bool IsPrime(BigInteger x, bool pass)
        {
            return IsPrime(x, 25, pass);
        }

        //***********************************************************************
        // Probabilistic prime test based on Rabin-Miller's
        //
        // for any p > 0 with p - 1 = 2^s * t
        //
        // p is probably prime (strong pseudoprime) if for any a < p,
        // 1) a^t mod p = 1 or
        // 2) a^((2^j)*t) mod p = p-1 for some 0 <= j <= s-1
        //
        // Otherwise, p is composite.
        //
        // Returns
        // -------
        // True if "this" is a strong pseudoprime to randomly chosen
        // bases.  The number of chosen bases is given by the "confidence"
        // parameter.
        //
        // False if "this" is definitely NOT prime.
        //
        //***********************************************************************

        public override bool Helper(BigInteger thisVal, int confidence)
        {
            // calculate values of s and t

            BigInteger p_sub1 = thisVal - (new BigInteger(1));
            int s = 0;

            for (int index = 0; index < p_sub1.dataLength; index++)
            {
                uint mask = 0x01;

                for (int i = 0; i < 32; i++)
                {
                    if ((p_sub1.GetDataAt(index) & mask) != 0)
                    {
                        index = p_sub1.dataLength;      // to break the outer loop
                        break;
                    }
                    mask <<= 1;
                    s++;
                }
            }

            BigInteger t = p_sub1 >> s;

            int bits = thisVal.bitCount();
            BigInteger a;
            if (confidence == 0)
            {
                a = 2;
                confidence = 1;
            }
            else
            {
                a = new BigInteger();
            }
            Random rand = new Random();

            for (int round = 0; round < confidence; round++)
            {
                bool done = false;

                while (!done && !(confidence == 1 && a == 2))		// generate a < n
                {
                    int testBits = 0;

                    // make sure "a" has at least 2 bits
                    while (testBits < 2)
                        testBits = (int)(rand.NextDouble() * bits);

                    a.genRandomBits(testBits, rand);

                    int byteLen = a.dataLength;

                    // make sure "a" is not 0
                    if (byteLen > 1 || (byteLen == 1 && a.IsZerothBitDiffOfOne()))
                        done = true;
                }

                // check whether a factor exists (fix for version 1.03)
                if (!(confidence == 1 && a == 2)){
                    BigInteger gcdTest = a.gcd(thisVal);
                    if (gcdTest.dataLength == 1 && gcdTest.IsZerothBitDiffOfOne())
                    {
                        return false;
                    }
                }
                BigInteger b = a.modPow(t, thisVal);
                bool result = false;

                if (b.dataLength == 1 && !b.IsZerothBitDiffOfOne())         // a^t mod p = 1
                    result = true;

                for (int j = 0; result == false && j < s; j++)
                {
                    if (b == p_sub1)         // a^((2^j)*t) mod p = p-1 for some 0 <= j <= s-1
                    {
                        result = true;
                        break;
                    }

                    b = (b * b) % thisVal;
                }

                if (result == false)
                    return false;
            }

            return true;
        }
    }
}
